﻿/*=====================================================================================
 * 
 * FILE: PartitioningTree.cs
 * AUTH: Matthew Baum, 9753095
 * DATE: 03/01/2012
 * LAST: 03/17/2012
 * 
 * DESC:    - QuadTree Implementation
 *          - BVH Implementation (bounding boxes)
 *          - Designed for use on 2.5-D Levels
 *          - Depth is based on desired "bucket size" (count for each leaf node)
 *          - Tree is constructed by insertion
 *
 *=====================================================================================*/ 


// Using directives
using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;


// Class declarations
namespace RisingThreat
{
    // An interface for items that can be contained in a Quad Tree Partition
    interface QuadTreeItem
    {
        // Get bounding box
        BoundingBox getBoundingVolume();

        // Get faces
        Plane[] getFaces();
    }

    /*================================================================================== 
     * A Quad tree node/partition : The main Quad Tree class.
     * 
     * A tree is defined recursively, thus each subtree (partition) is itself a full
     * quad tree.
     * 
     * This tree is constructed by INSERTION.
     *==================================================================================*/ 
    class QuadPartition
    {
        // Position
        private Vector3 position;

        // Size
        private Vector3 size;

        // BoundingBox
        private BoundingBox boundingVolume;

        // Parent node
        private QuadPartition parent;

        // Bucket Count (determines partition depth)
        private int bucket_count;

        /*================================================================= 
         * Array of lower partitions (4 for a Quad Tree)
         * Partitions are numbered according to Cartesian Quadrants
         *=================================================================*/
        private QuadPartition[] partitions = {null, null, null, null};

        // List of Items stored at this node
        private List<QuadTreeItem> itemList = new List<QuadTreeItem>();

        // Constructor
        public QuadPartition(QuadPartition prnt, Vector3 pos, Vector3 sz, int count)
        {
            // Set parent node
            parent = prnt;

            // Set position
            position = pos;

            // Set size
            size = sz;

            // Set bounding volume
            setBoundingVolume();

            // Set count value
            bucket_count = count;
        }


        /*==================================================================
         * Recursively determine whether a given item is in collision with
         * anything in the tree.
         * 
         * NOTE: An item is referenced in every LEAF node
         * that its bounding volume is CONTAINED in,
         * or INTERSECTS with. Thus, a single collision may be detected a
         * number of times, but is eliminated using the HashSet ADT.
         *==================================================================*/
        public HashSet<QuadTreeItem> getPotentialCollisions(BoundingSphere sphere)
        {
            // The Set of tree items to be returned
            HashSet<QuadTreeItem> collisionSet = new HashSet<QuadTreeItem>();

            // Populate the set by searching through the tree
            searchCollisions(sphere, collisionSet);

            // Return the set
            return collisionSet;
        }

        // Private helper to find objects that MAY be colliding
        private void searchCollisions(BoundingSphere sphere, HashSet<QuadTreeItem> collisionSet)
        {
            // IF this partition is LEAF, add the items to the set
            if(isLeaf())
            {
                foreach(QuadTreeItem item in itemList)
                {
                    collisionSet.Add(item);
                }
            }

            // ELSE, try children
            else
            {
                foreach(QuadPartition partition in partitions)
                {
                    // IF this partition touches on the desired bounding volume
                    if(partition.touchesOn(sphere))
                    {
                        partition.searchCollisions(sphere, collisionSet);
                    }
                }
            }
        }

        /*==================================================================
         * Recursively determine whether a given ray is intersecting with
         * anything in the tree.
         * 
         * NOTE: An item is referenced in every LEAF node
         * that its bounding volume is CONTAINED in,
         * or INTERSECTS with. Thus, a single collision may be detected a
         * number of times, but is eliminated using the HashSet ADT.
         *==================================================================*/
        public HashSet<KeyValuePair<QuadTreeItem, float?>> getRayIntersections(Ray ray)
        {
            // The Set of tree items to be returned
            HashSet<KeyValuePair<QuadTreeItem, float?>> intersectionSet = new HashSet<KeyValuePair<QuadTreeItem, float?>>();
            
            // Populate the set by searching through the tree
            searchIntersections(ray, intersectionSet);

            // Return the set
            return intersectionSet;
        }

        // Private helper to find objects that intersect a given ray
        private void searchIntersections(Ray ray, HashSet<KeyValuePair<QuadTreeItem, float?>> intersectionSet)
        {
            // Value to hold intersection distance
            float? dist;

            // IF this partition is LEAF, add the items to the set
            if(isLeaf())
            {
                foreach(QuadTreeItem item in itemList)
                {
                    dist = ray.Intersects(item.getBoundingVolume());

                    
                    // IF this partition intersects the ray at the proper distance
                    if(dist <= 5.0f)
                    {
                        intersectionSet.Add(new KeyValuePair<QuadTreeItem, float?>(item, dist));
                    }
                     
                }
            }

            // ELSE, try children
            else
            {
                foreach(QuadPartition partition in partitions)
                {
                    
                    // IF this partition intersects the ray at the proper distance
                    if(ray.Intersects(partition.boundingVolume) <= 5.0f)
                    {
                        partition.searchIntersections(ray, intersectionSet);
                    }
                     
                }
            }
        }


        /*==================================================================
         * Recursively insert an item at a given node.
         * Users will typically insert at the "partition"/node
         * representing the root of their quadtree.
         * 
         * NOTE: An item is referenced in every LEAF node
         * that its bounding volume is CONTAINED in,
         * or INTERSECTS with.
         *==================================================================*/
        public void insert(QuadTreeItem item)
        {
            // If this partition DOES NOT touch on the item, RETURN now!
            if (!touchesOn(item.getBoundingVolume()))
            {
                return;
            }

            // ELSE IF this node is leaf, AND capacity is okay: insert here
            else if (isLeaf() && itemList.Count < bucket_count)
            {
                itemList.Add(item);
            }

            // ELSE IF this node is leaf, AND capacity is exceeded: partition
            else if (isLeaf() && itemList.Count >= bucket_count)
            {
                // Partition
                partition();

                // Insert (recurse)
                insert(item);
            }

            // ELSE, not leaf: try children
            else
            {
                partitions[0].insert(item);
                partitions[1].insert(item);
                partitions[2].insert(item);
                partitions[3].insert(item);
            }
        }


        // Re-insert items stored at this node (update on partition)
        private void reinsert()
        {
            // Insert items at this node again (should trickle down)
            foreach (QuadTreeItem item in itemList)
            {
                if (item != null)
                {
                    insert(item);
                }
            }

            // Empty the list at this node
            itemList.Clear();
        }

        // Partition this node into 4 equal quadrants
        private void partition()
        {
            // Create 4 new nodes to set the partitions
            QuadPartition qp1, qp2, qp3, qp4;

            // New size for partitions
            Vector3 partSize = new Vector3(size.X / 2, size.Y, size.Z / 2);

            // Set position for the first quad partition
            qp1 = new QuadPartition
                (
                    this,
                    new Vector3( position.X + size.X / 4, position.Y, position.Z - size.Z / 4 ),
                    partSize,
                    bucket_count
                );

            // Set position for the second quad partition
            qp2 = new QuadPartition
                (
                    this,
                    new Vector3(position.X - size.X / 4, position.Y, position.Z - size.Z / 4),
                    partSize,
                    bucket_count
                );

            // Set position for the third quad partition
            qp3 = new QuadPartition
                (
                    this,
                    new Vector3(position.X - size.X / 4, position.Y, position.Z + size.Z / 4),
                    partSize,
                    bucket_count
                );

            // Set position for the fourth quad partition
            qp4 = new QuadPartition
                (
                    this,
                    new Vector3(position.X + size.X / 4, position.Y, position.Z + size.Z / 4),
                    partSize,
                    bucket_count
                );

            // Add the partitions to the current node
            partitions[0] = qp1;
            partitions[1] = qp2;
            partitions[2] = qp3;
            partitions[3] = qp4;

            // Re-insert all Items stored at this node, so they are in leaf nodes
            reinsert();
        }

        // Compute the height of this quadtree
        public int getHeight()
        {
            // TERMINAL CONDITION: Leaf Partition
            if(isLeaf())
            {
                return 0;
            }

            // ELSE, get the highest value from its children, plau one (current level)
            else
            {
                return 
                ( 
                    Math.Max
                    (
                        Math.Max(partitions[0].getHeight(), partitions[1].getHeight() ),
                        Math.Max(partitions[2].getHeight(), partitions[3].getHeight() )
                    )
                    + 1
                );
            }
        }

        /*================================================================= 
         * Determine if the current node's bounding volume contains
         * or intersects with a given item (boundingVolume).
         *=================================================================*/
        private bool touchesOn(BoundingBox box)
        {
            ContainmentType contains = boundingVolume.Contains(box);

            return
            (
                contains.HasFlag(ContainmentType.Contains) ||
                contains.HasFlag(ContainmentType.Intersects)
            );
        }

        private bool touchesOn(BoundingSphere sphere)
        {
            ContainmentType contains = boundingVolume.Contains(sphere);

            return
            (
                contains.HasFlag(ContainmentType.Contains) ||
                contains.HasFlag(ContainmentType.Intersects)
            );
        }

        /* =================================================================
         * Determine whether or not the current node has lower partitions
         * Is it a leaf?
         */
        private bool isLeaf()
        {
            // Return result
            bool isPartitioned = false;

            // IF all children are NULL, set to TRUE
            if
            (
                partitions[0] == null &&
                partitions[1] == null &&
                partitions[2] == null &&
                partitions[3] == null
            )
            {
                isPartitioned = true;
            }

            // Return the result
            return isPartitioned;
        }


        // *** GETTERS AND SETTERS *** //
        // GET position
        public Vector3 getPosition()
        {
            return position;
        }

        // SET position
        public void setPosition(Vector3 pos)
        {
            position = pos;
        }

        // GET bounding volume
        public BoundingBox getBoundingVoume()
        {
            return boundingVolume;
        }

        // SET/update bounding volume
        private void setBoundingVolume()
        {
            /* 
             * Use position and size to determine min and max
             * Points to include in box.
             */
            Vector3 min, max;
            min = new Vector3(position.X - size.X / 2, position.Y - size.Y / 2, position.Z - size.Z / 2);
            max = new Vector3(position.X + size.X / 2, position.Y + size.Y / 2, position.Z + size.Z / 2);

            // Set the new Bounding box
            boundingVolume = new BoundingBox(min, max);
        }

        // Get total item count for this tree, recursively
        public int getCount()
        {
            // TERMINAL CONDITION: Leaf Node
            if(isLeaf())
            {
                return itemList.Count;
            }

            // ELSE, try children
            else
            {
                return
                (
                    partitions[0].getCount() +
                    partitions[1].getCount() +
                    partitions[2].getCount() +
                    partitions[3].getCount()
                );
            }
        }
    }
}
